<!DOCTYPE html><html class="appearance-light" lang="zh-CN"><head><meta charset="UTF-8"><title>Acwing寒假每日一题(入门组) 打卡记录 题解</title><meta name="description" content="如你所见, 希望做个能言善道的人"><meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no, initial-scale=1"><!-- Google Analytics --><!-- End Google Analytics -->
<!-- Baidu Analytics --><!-- End Baidu Analytics --><link rel="icon" href="/images/touxiang.jpg"><link rel="stylesheet" href="/style/common/bulma.css"><link rel="stylesheet" href="/style/base.css"><link rel="stylesheet" href="/style/icon.css"><link rel="stylesheet" href="/style/common/helper.css"><script src="/js/common.js"></script><link rel="stylesheet" href="/style/post.css"><link rel="stylesheet" href="/style/themes/highlight-theme-light.css"><script src="/js/highlight.pack.js"></script><meta name="description" content="(活动已结束)寒假组队学习算法，闫老师带领大家每日刷一道经典算法题。题目难度：入门级别。


欢迎来Acwing围观我点击标题，进入题目。
Acwing 3257. 跳一跳每日一题要结束了! 庆祝自己按时全部打卡成功!
参考代码#include&amp;lt;iostream&amp;gt;
using namespace std;

int main() &amp;#123;
    int n, last = 0;
    int ans = 0;
    while (cin &amp;gt;&amp;gt; n, n) &amp;#123;
        if (n == 1) ++ans, last = 0;
        else last += 2, ans += last;
    &amp;#125;
    cout &amp;lt;&amp;lt; a.."><meta name="generator" content="Hexo 5.4.0"></head><body class="is-flex is-flex-direction-column"><header class="header-widget is-flex-shrink-0 is-hidden-mobile"><div class="container is-fullhd is-flex is-justify-content-space-between is-align-items-center is-full-height"><section class="is-hidden-mobile is-flex-shrink-0"><h2><a href="/">insight's blog</a></h2></section><h3 class="is-hidden-mobile is-family-serif is-full-height is-flex is-align-items-center is-flex-shrink-0"><div class="is-full-height" id="postTopic"><p class="is-full-height is-flex-shrink-0 is-flex is-align-items-center is-justify-content-center">Acwing寒假每日一题(入门组) 打卡记录 题解</p><p class="is-full-height is-flex-shrink-0 is-flex is-align-items-center is-justify-content-center">点击返回顶部</p></div></h3><aside class="is-flex-shrink-0"><h3 class="is-inline-block"><a href="/">首页</a></h3><h3 class="is-inline-block"><a href="/about">关于</a></h3><h3 class="is-inline-block"><a href="/archives">归档</a></h3></aside></div></header><header class="is-flex header-widget is-flex-shrink-0 is-align-items-center is-justify-content-center is-hidden-tablet"><h3 class="is-inline-block"><a href="/">首页</a></h3><h3 class="is-inline-block"><a href="/about">关于</a></h3><h3 class="is-inline-block"><a href="/archives">归档</a></h3></header><main><main class="container is-max-widescreen content section post-page pt-4 px-4"><div class="columns is-flex-desktop is-justify-content-center is-flex-direction-row-reverse"><div class="column is-3 is-hidden-mobile"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-3257-%E8%B7%B3%E4%B8%80%E8%B7%B3"><span class="toc-text">Acwing 3257. 跳一跳</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-3227-%E6%8A%98%E7%82%B9%E8%AE%A1%E6%95%B0"><span class="toc-text">Acwing 3227. 折点计数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-1"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-3232-%E6%9C%80%E5%A4%A7%E6%B3%A2%E5%8A%A8"><span class="toc-text">Acwing 3232. 最大波动</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-2"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-3203-%E7%94%BB%E5%9B%BE"><span class="toc-text">Acwing 3203. 画图</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%AE%A1%E6%95%B0%E7%BB%9F%E8%AE%A1"><span class="toc-text">计数统计</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-3"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-3208-Z%E5%AD%97%E5%BD%A2%E6%89%AB%E6%8F%8F"><span class="toc-text">Acwing 3208. Z字形扫描</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A8%A1%E6%8B%9F"><span class="toc-text">模拟</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-4"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-1477-%E6%8B%BC%E5%86%99%E6%AD%A3%E7%A1%AE"><span class="toc-text">Acwing 1477. 拼写正确</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-5"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-445-%E6%95%B0%E5%AD%97%E5%8F%8D%E8%BD%AC"><span class="toc-text">Acwing 445. 数字反转</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-6"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-449-%E8%B4%A8%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3"><span class="toc-text">Acwing 449. 质因数分解</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9E%9A%E4%B8%BE"><span class="toc-text">枚举</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-7"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-441-%E6%95%B0%E5%AD%97%E7%BB%9F%E8%AE%A1"><span class="toc-text">Acwing 441. 数字统计</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A8%A1%E6%8B%9F-%E6%9E%9A%E4%B8%BE"><span class="toc-text">模拟 + 枚举</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-8"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-458-%E6%AF%94%E4%BE%8B%E7%AE%80%E5%8C%96"><span class="toc-text">Acwing 458. 比例简化</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9A%B4%E5%8A%9B%E6%9E%9A%E4%B8%BE"><span class="toc-text">暴力枚举</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-9"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-425-%E6%98%8E%E6%98%8E%E7%9A%84%E9%9A%8F%E6%9C%BA%E6%95%B0"><span class="toc-text">Acwing 425. 明明的随机数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-text">计数排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-10"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-417-%E4%B8%8D%E9%AB%98%E5%85%B4%E7%9A%84%E6%B4%A5%E6%B4%A5"><span class="toc-text">Acwing 417. 不高兴的津津</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-11"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-421-%E9%99%B6%E9%99%B6%E6%91%98%E8%8B%B9%E6%9E%9C"><span class="toc-text">Acwing 421. 陶陶摘苹果</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A8%A1%E6%8B%9F-1"><span class="toc-text">模拟</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-12"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-428-%E6%95%B0%E5%88%97"><span class="toc-text">Acwing 428. 数列</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E8%BF%9B%E5%88%B6%E6%9E%9A%E4%B8%BE-%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="toc-text">二进制枚举 + 快速幂</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-13"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-433-ISBN%E5%8F%B7%E7%A0%81"><span class="toc-text">Acwing 433. ISBN号码</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%A4%84%E7%90%86-%E6%A8%A1%E6%8B%9F"><span class="toc-text">字符串处理 + 模拟</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-14"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Acwing-89-a-b"><span class="toc-text">Acwing 89. a^b</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9A%B4%E5%8A%9B%E8%BF%90%E7%AE%97"><span class="toc-text">暴力运算</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-15"><span class="toc-text">参考代码</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="toc-text">快速幂</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81-16"><span class="toc-text">参考代码</span></a></li></ol></li></ol></li></ol></div><div class="column is-9"><header class="my-4"></header><h1 class="mt-0 mb-1 is-family-serif" id="postTitle">Acwing寒假每日一题(入门组) 打卡记录 题解</h1><time class="has-text-grey" datetime="2021-06-21T04:22:40.363Z">2021-06-21</time><article class="mt-2 post-content"><p>(活动已结束)<br>寒假组队学习算法，闫老师带领大家每日刷一道经典算法题。<br>题目难度：入门级别。</p>
<span id="more"></span>

<p><a target="_blank" rel="noopener" href="https://www.acwing.com/user/myspace/index/34956/">欢迎来Acwing围观我</a><br>点击标题，进入题目。</p>
<h2 id="Acwing-3257-跳一跳"><a href="#Acwing-3257-跳一跳" class="headerlink" title="Acwing 3257. 跳一跳"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/3260/">Acwing 3257. 跳一跳</a></h2><p>每日一题要结束了! 庆祝自己按时全部打卡成功!</p>
<h3 id="参考代码"><a href="#参考代码" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int main() &#123;
    int n, last = 0;
    int ans = 0;
    while (cin &gt;&gt; n, n) &#123;
        if (n == 1) ++ans, last = 0;
        else last += 2, ans += last;
    &#125;
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-3227-折点计数"><a href="#Acwing-3227-折点计数" class="headerlink" title="Acwing 3227. 折点计数"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/3230/">Acwing 3227. 折点计数</a></h2><p>和昨天一样的水题</p>
<h3 id="参考代码-1"><a href="#参考代码-1" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

const int N = 1005;
int ans, a[N];
int main() &#123;
    int n; cin &gt;&gt; n;
    
    for (int i = 0; i &lt; n; ++i) &#123;
        cin &gt;&gt; a[i];
    &#125;
    --n;
    for (int i = 1; i &lt; n; ++i) &#123;
        if (a[i - 1] &lt; a[i] &amp;&amp; a[i] &gt; a[i + 1] || a[i - 1] &gt; a[i] &amp;&amp; a[i] &lt; a[i + 1])
            ++ans;
    &#125;
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-3232-最大波动"><a href="#Acwing-3232-最大波动" class="headerlink" title="Acwing 3232. 最大波动"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/3235/">Acwing 3232. 最大波动</a></h2><p>好水的题 直接枚举前后两天之差即可</p>
<h3 id="参考代码-2"><a href="#参考代码-2" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

const int N = 1005;
int a[N];
int main() &#123;
    int n; cin &gt;&gt; n;
    
    for (int i = 0; i &lt; n; ++i) cin &gt;&gt; a[i];
    
    int ans = 0;
    for (int i = 1; i &lt; n; ++i) &#123;
        ans = max(ans, abs(a[i] - a[i - 1]));
    &#125;
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-3203-画图"><a href="#Acwing-3203-画图" class="headerlink" title="Acwing 3203. 画图"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/3206/">Acwing 3203. 画图</a></h2><h3 id="计数统计"><a href="#计数统计" class="headerlink" title="计数统计"></a>计数统计</h3><p>对于这种<strong>只需要计数, 不需要考虑重复数据</strong>的题目<br>能想到的好办法就是计数<br>从起始坐标遍历到结束坐标, 每个方格用某个角的坐标来描述, 记录坐标即可<br>我在这里选择左下角<br>时间复杂度 $O(XYN)$<br>每组数据都要遍历 $|X| * |Y|$ 次, $|X| \enspace |Y|$ 为横/纵坐标之差, 一共有 $N$ 组 </p>
<h3 id="参考代码-3"><a href="#参考代码-3" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

const int N = 101;
bool st[N][N];

int main() &#123;
    int n; cin &gt;&gt; n;
    
    int x1, y1, x2, y2;
    /* 输入 */
    for (int i = 0; i &lt; n; ++i) &#123;
        cin &gt;&gt; x1 &gt;&gt; y1 &gt;&gt; x2 &gt;&gt; y2;
        /* 开始遍历 记录左下角 */
        for (int x = x1; x &lt; x2; ++x)
            for (int y = y1; y &lt; y2; ++y) 
                /* 标记 */
                st[x][y] = 1;
    &#125;
    
    /* 统计 */
    int ans = 0;
    for (int i = 0; i &lt; N; ++i)
        for (int j = 0; j &lt; N; ++j)
            ans += st[i][j];
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-3208-Z字形扫描"><a href="#Acwing-3208-Z字形扫描" class="headerlink" title="Acwing 3208. Z字形扫描"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/3211/">Acwing 3208. Z字形扫描</a></h2><p>找规律, 模拟</p>
<h3 id="模拟"><a href="#模拟" class="headerlink" title="模拟"></a>模拟</h3><p>一个矩阵一共有 $2n-1$ 条对角线<br>把对角线分成两类 右上和左下<br>对于每一条对角线 都有 $x + y = C1 \enspace x - y = C2$<br>也就是说 对角线的坐标之差/坐标之和是固定的<br>因此可以利用这个关系来算坐标<br>最后判断一下边界即可<br>因为减法肯定不会超出矩阵范围 所以使用减法比较方便<br>时间复杂度 $O(N^2)$</p>
<h3 id="参考代码-4"><a href="#参考代码-4" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

const int N = 505;
int a[N][N];

int main() &#123;
    int n; cin &gt;&gt; n;
    for (int i = 0; i &lt; n; ++i)
        for (int j = 0; j &lt; n; ++j) 
            cin &gt;&gt; a[i][j];
    
    // 对角线个数
    int len = n &lt;&lt; 1; 
    // 循环2n - 1 次
    for (int i = 0; i &lt; len; ++i) &#123;
        // 从第0条开始 第0条是右上
        // 因此偶数右上 奇数左下
        if (i &amp; 1) &#123;
            // 奇数左下
            for (int j = 0; j &lt;= i; ++j) &#123;
                // 判断边界
                if (j &gt;= 0 &amp;&amp; j &lt; n &amp;&amp; i - j &gt;= 0 &amp;&amp; i - j &lt; n)
                    cout &lt;&lt; a[j][i - j] &lt;&lt; &#39; &#39;;
            &#125;
        &#125; else &#123;
            // 偶数右上
            for (int j = i; ~j; --j) &#123;
                // 判断边界
                if (j &gt;= 0 &amp;&amp; j &lt; n &amp;&amp; i - j &gt;= 0 &amp;&amp; i - j &lt; n)
                    cout &lt;&lt; a[j][i - j] &lt;&lt; &#39; &#39;;
            &#125;
        &#125;
    &#125;
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-1477-拼写正确"><a href="#Acwing-1477-拼写正确" class="headerlink" title="Acwing 1477. 拼写正确"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/1479/">Acwing 1477. 拼写正确</a></h2><p>连续几日都是模拟, 数字, 字符串处理</p>
<h3 id="参考代码-5"><a href="#参考代码-5" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
#include&lt;cstring&gt;

using namespace std;

string s;
string num[12] = &#123;&quot;zero&quot;, &quot;one&quot;, &quot;two&quot;, &quot;three&quot;, &quot;four&quot;, &quot;five&quot;, &quot;six&quot;, &quot;seven&quot;, &quot;eight&quot;, &quot;nine&quot;&#125;;
int main() &#123;
    cin &gt;&gt; s;
    
    int sum = 0;
    for (int i = 0; i &lt; s.size(); ++i) sum += s[i] - &#39;0&#39;;

    string ans = to_string(sum);
    for (int i = 0; i &lt; ans.size(); ++i) cout &lt;&lt; num[ans[i] - &#39;0&#39;] &lt;&lt; &#39; &#39;;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-445-数字反转"><a href="#Acwing-445-数字反转" class="headerlink" title="Acwing 445. 数字反转"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/447/">Acwing 445. 数字反转</a></h2><p>直接模拟, 注意负号和前导0的处理</p>
<h3 id="参考代码-6"><a href="#参考代码-6" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int main() &#123;
    /* 做法一 直接逆序输出 */
    /*
    string s; cin &gt;&gt; s;
    
    while (s.back() == &#39;0&#39;) s.pop_back();
    
    bool flag = s[0] == &#39;-&#39;;
    if (flag) cout &lt;&lt; &#39;-&#39;;
    for (int i = s.size() - 1; i &gt; 0; --i) cout &lt;&lt; s[i];
    if (!flag) cout &lt;&lt; s[0];
    */
    /* 做法二 逆序处理再输出 */
    int n; cin &gt;&gt; n;
    if (n &lt; 0) n = -n, cout &lt;&lt; &#39;-&#39;;
    int ans = 0;
    for (; n; n /= 10) &#123;
        ans = ans * 10 + n % 10;
    &#125;
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-449-质因数分解"><a href="#Acwing-449-质因数分解" class="headerlink" title="Acwing 449. 质因数分解"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/451/">Acwing 449. 质因数分解</a></h2><p>数论题</p>
<h3 id="枚举"><a href="#枚举" class="headerlink" title="枚举"></a>枚举</h3><p>从小到大枚举约数 然后输出大的约数即可<br>理论支持:</p>
<ol>
<li>一个数肯定能被分解成质数乘积的形式</li>
<li>如果一个数能被非质数整除 那这个非质数也能分解成质数乘积 而质数乘积肯定小于非质数本身</li>
<li>因为是从小到大枚举 再加上第2点 不可能枚举到能分解成质数乘积的非质数</li>
</ol>
<h3 id="参考代码-7"><a href="#参考代码-7" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int main() &#123;
    int n; cin &gt;&gt; n;
    for (int i = 2; ; ++i) &#123;
        if (!(n % i)) &#123;
            cout &lt;&lt; n / i;
            break;
        &#125;
    &#125;
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-441-数字统计"><a href="#Acwing-441-数字统计" class="headerlink" title="Acwing 441. 数字统计"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/443/">Acwing 441. 数字统计</a></h2><h3 id="模拟-枚举"><a href="#模拟-枚举" class="headerlink" title="模拟 + 枚举"></a>模拟 + 枚举</h3><p>数字求和, 求某个数字的个数等等, 都是枚举数字的每一位<br>直接用模板即可<br>时间复杂度 $O(NlogN)$</p>
<h3 id="参考代码-8"><a href="#参考代码-8" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int getTwo(int x) &#123;
    int ret = 0;
    for (; x; x /= 10) &#123;
        ret += x % 10 == 2;
    &#125;
    return ret;
&#125;

int main() &#123;
    int l, r;
    cin &gt;&gt; l &gt;&gt; r;
    
    int cnt = 0;
    for (int i = l; i &lt;= r; ++i) cnt += getTwo(i);
    cout &lt;&lt; cnt;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-458-比例简化"><a href="#Acwing-458-比例简化" class="headerlink" title="Acwing 458. 比例简化"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/460/">Acwing 458. 比例简化</a></h2><p>标签上写着二分, 想了个双重二分放弃, 直接暴力双重循环(doge</p>
<h3 id="暴力枚举"><a href="#暴力枚举" class="headerlink" title="暴力枚举"></a>暴力枚举</h3><p>直接枚举并按照条件筛选最优解<br>不过这里有个优化, 不用判断是否互质, 可以使用一下反证法<br>因为我们是从小到大枚举, 如果存在 $gcd(A_1, B_1) = C \enspace != 1$, 且 $A_1, B_1$ 的比例最接近原来的比例<br>那么一定可以通过约去公约数, 得到新的两个数, 这两个数互质且也最接近原来的比例<br>即 $(A_1 / C) / (B_1 / C) = A_2 / B_2$, $gcd(A_2, B_2) = 1$ 且 $A_2, B_2$ 的比例也最接近原来的比例<br>显然$A_2, B_2$ 是小于 $A_1, B_1$的, 也就是说会提前枚举到, 因此我们取到的答案肯定是互质的<br>时间复杂度 $O(N^2)$</p>
<h3 id="参考代码-9"><a href="#参考代码-9" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include &lt;iostream&gt;
using namespace std;

int main()
&#123;
    int A, B, L;
    cin &gt;&gt; A &gt;&gt; B &gt;&gt; L;

    int a, b;
    double delta = 1e9;
    double X = A * 1.0 / B;
    for (int i = 1; i &lt;= L; i ++ )
        for (int j = 1; j &lt;= L; j ++ ) &#123;
            double x = i * 1.0 / j;
            if (x &gt;= X &amp;&amp; x - X &lt; delta) &#123;
                delta = x - X;
                a = i, b = j;
            &#125;
        &#125;

    cout &lt;&lt; a &lt;&lt; &#39; &#39; &lt;&lt; b &lt;&lt; endl;

    return 0;
&#125;
</code></pre>
<h2 id="Acwing-425-明明的随机数"><a href="#Acwing-425-明明的随机数" class="headerlink" title="Acwing 425. 明明的随机数"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/427/">Acwing 425. 明明的随机数</a></h2><p>经典桶排序, 可以当作模板了</p>
<h3 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h3><p>严格来说这是计数排序, 不是桶排序<br>空间换时间的一种应用, 开一个长度和最大数据相同的数组<br>然后把数据当作索引, 数组的值用来记录数据出现的次数<br>最后直接遍历这个数组, 数组值不为0就说明有这个数据<br>输出即是排序好的数据</p>
<h3 id="参考代码-10"><a href="#参考代码-10" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;

using namespace std;

const int N = 1005;
int cnt[N];

int main() &#123;
    int n; cin &gt;&gt; n;
    
    int t;
    int m = 0;
    while (n--) &#123;
        cin &gt;&gt; t;
        if (!cnt[t]) ++m, cnt[t] = 1;
        /* 骚操作版本 利用位运算消除if */
        // m += !cnt[t] &amp; 1;
        // cnt[t] = 1;
    &#125;

    cout &lt;&lt; m &lt;&lt; endl;
    for (int i = 0; i &lt; N; ++i) &#123;
        if (cnt[i]) cout &lt;&lt; i &lt;&lt; &#39; &#39;;
    &#125;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-417-不高兴的津津"><a href="#Acwing-417-不高兴的津津" class="headerlink" title="Acwing 417. 不高兴的津津"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/419/">Acwing 417. 不高兴的津津</a></h2><p>今天也是一道<del>水题</del>模拟呢</p>
<h3 id="参考代码-11"><a href="#参考代码-11" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int main() &#123;
    int ans = -1, day;
    int a, b;
    int cnt = 7;
    
    for (int i = 1; i &lt; 8; ++i) &#123;
        cin &gt;&gt; a &gt;&gt; b;
        int t = a + b;
        if (ans &lt; t) ans = t, day = i;
    &#125;
    
    cout &lt;&lt; (ans &gt; 8 ? day : 0);
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-421-陶陶摘苹果"><a href="#Acwing-421-陶陶摘苹果" class="headerlink" title="Acwing 421. 陶陶摘苹果"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/423/">Acwing 421. 陶陶摘苹果</a></h2><p>难得出现一道水题, 估计是在给后面的题目铺垫</p>
<h3 id="模拟-1"><a href="#模拟-1" class="headerlink" title="模拟"></a>模拟</h3><p>直接按照题目要求, 进行模拟即可</p>
<h3 id="参考代码-12"><a href="#参考代码-12" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int a[10];
int main() &#123;
    for (int i = 0; i &lt; 10; ++i) cin &gt;&gt; a[i];
    
    int init; cin &gt;&gt; init;
    init += 30;
    
    int ans = 0;
    for (int i = 0; i &lt; 10; ++i) ans += init &gt;= a[i];
    
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-428-数列"><a href="#Acwing-428-数列" class="headerlink" title="Acwing 428. 数列"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/430/">Acwing 428. 数列</a></h2><h3 id="二进制枚举-快速幂"><a href="#二进制枚举-快速幂" class="headerlink" title="二进制枚举 + 快速幂"></a>二进制枚举 + 快速幂</h3><p>仔细观察数列，可以发现第 $n$ 项的公式和 $n$ 的二进制位有关<br>因此直接枚举二进制的每一位，然后求幂的时候使用快速幂即可<br>时间复杂度 $O(klog(n))$</p>
<h3 id="参考代码-13"><a href="#参考代码-13" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

int get(int a, int b) &#123;
    int ret = 1;
    while (b) &#123;
        if (b &amp; 1) ret *= a;
        b &gt;&gt;= 1;
        a *= a;
    &#125;
    return ret;
&#125;

int main() &#123;
    int k, n;
    cin &gt;&gt; k &gt;&gt; n;
    
    int ans = 0;
    //枚举每一位
    for (int i = 0; n; ++i) &#123;
        //如果为1说明需要进行运算
        if (n &amp; 1) ans += get(k, i);
        //左移准备处理下一位
        n &gt;&gt;= 1;
    &#125;
    cout &lt;&lt; ans;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-433-ISBN号码"><a href="#Acwing-433-ISBN号码" class="headerlink" title="Acwing 433. ISBN号码"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/435/">Acwing 433. ISBN号码</a></h2><h3 id="字符串处理-模拟"><a href="#字符串处理-模拟" class="headerlink" title="字符串处理 + 模拟"></a>字符串处理 + 模拟</h3><p>直接根据题意，对字符串进行处理即可</p>
<h3 id="参考代码-14"><a href="#参考代码-14" class="headerlink" title="参考代码"></a>参考代码</h3><pre><code class="c++">#include&lt;iostream&gt;
using namespace std;

char s[15];

int main() &#123;
    cin &gt;&gt; s;
    int cnt = 2;
    int sum = s[0] - &#39;0&#39;;
    for (int i = 2; i &lt; 5; ++i) &#123;
        sum += (s[i] - &#39;0&#39;) * cnt++;
    &#125;
    for (int i = 6; i &lt; 11; ++i) &#123;
        sum += (s[i] - &#39;0&#39;) * cnt++;
    &#125;
    sum %= 11;
    char goal = sum == 10 ? &#39;X&#39; : sum + &#39;0&#39;;
    if (goal == s[12]) cout &lt;&lt; &quot;Right&quot; &lt;&lt; endl;
    else &#123;
        s[12] = goal;
        cout &lt;&lt; s;
    &#125;
    
    return 0;
&#125;
</code></pre>
<h2 id="Acwing-89-a-b"><a href="#Acwing-89-a-b" class="headerlink" title="Acwing 89. a^b"></a><a target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/91/">Acwing 89. a^b</a></h2><h3 id="暴力运算"><a href="#暴力运算" class="headerlink" title="暴力运算"></a>暴力运算</h3><p>直接循环计算，时间复杂度 $O(n)$<br>缺点：当幂数过大容易超时</p>
<h4 id="参考代码-15"><a href="#参考代码-15" class="headerlink" title="参考代码"></a>参考代码</h4><pre><code class="c++">int pow(int a, int b, int p) &#123;
    int ret = 1;
    while (b--) &#123;
        ret = 1LL * ret * a % p;
        a = 1LL * a * a % p;
    &#125;
    return ret % p;
&#125;
</code></pre>
<h3 id="快速幂"><a href="#快速幂" class="headerlink" title="快速幂"></a>快速幂</h3><p>利用二进制思想，转化为加权运算，减少不必要的运算，时间复杂度$O(log_2(n))$</p>
<h4 id="参考代码-16"><a href="#参考代码-16" class="headerlink" title="参考代码"></a>参考代码</h4><pre><code class="c++">int pow(int a, int b, int p) &#123;
    int ret = 1;
    while (b) &#123;
        if (b &amp; 1)
            ret = 1LL * ret * a % p;
        a = 1LL * a * a % p;
        b &gt;&gt;= 1;
    &#125;
    return ret % p;
&#125;
</code></pre>
</article><section class="jump-container is-flex is-justify-content-space-between my-6"><!-- em is empty placeholder--><a class="button is-default" href="/archives/465097960/" title="Acwing寒假每日一题(提高组) 打卡记录 题解"><i class="iconfont icon-prev mr-2 has-text-grey"></i><span class="has-text-weight-semibold">上一页: Acwing寒假每日一题(提高组) 打卡记录 题解</span></a><a class="button is-default" href="/archives/3674455572/" title="Acwing算法进阶指南 0x02 打卡 题解"><span class="has-text-weight-semibold">下一页: Acwing算法进阶指南 0x02 打卡 题解</span><i class="iconfont icon-next ml-2 has-text-grey"></i></a></section><article class="mt-6 comment-container"><script async src="https://utteranc.es/client.js" issue-term="pathname" theme="preferred-color-scheme"></script></article></div></div></main></main><footer class="is-flex is-flex-direction-column is-align-items-center is-flex-shrink-0 is-family-serif"><section class="sns-container"><!-- Github--><a title="github" target="_blank" rel="noopener nofollow" href="//github.com/insight-21"><i class="iconfont icon-github"></i></a><!-- Gitee--><a title="gitee" target="_blank" rel="noopener nofollow" href="//gitee.com/insight21"><i class="iconfont icon-gitee"></i></a><!-- Ins--><!-- RSS--><!-- 知乎--><!-- 领英--><!-- 脸书--></section><p><span>Copyright ©</span><span> insight 2021</span></p><div class="is-flex is-justify-content-center is-flex-wrap-wrap"><p>Powered by Hexo &verbar;&nbsp;</p><p class="is-flex is-justify-content-center"><a title="Hexo theme author" target="_blank" rel="noopener" href="//github.com/haojen">Theme by Haojen&nbsp;</a></p><div style="margin-top: 2px"><a class="github-button" title="github-button" target="_blank" rel="noopener" href="https://github.com/haojen/hexo-theme-Claudia" data-color-scheme="no-preference: light; light: light; dark: dark;" data-show-count="true"></a></div></div><div><span></span></div></footer><script async defer src="https://buttons.github.io/buttons.js"></script><script src="/js/post.js"></script></body></html>